/*
 *
 *  File: 'boggle.h'
 *
 *  Author: Samip Shah <samipshah@alumni.cmu.edu>
 *  Date: Sep 08, 2011
 *
 */

#ifndef INCLUDED_BOGGLE_H
#define INCLUDED_BOGGLE_H

#include <graph.h>
#include <SPCounter.h>
#include <stdlib.h>
#include <string.h>
#include <trie.h>
#include <time.h>

#define MAX_DICES 16

class Boggle 
{
  static const char* boggle_dices[MAX_DICES];

  enum Result {
    NO_PATH_FOUND,
    SUCCESS,
    NO_SUCH_WORD,
    NO_PATH_NO_WORD
  };

	Graph<short> boggle_board; 
  Trie<char> dict;
	char** board;
	int length;
	int width;
	unsigned char count[26];

  // helper functions
	short returnKey(char letter, int x, int y)
	{
		unsigned char cnt = count[letter - 'a'];
		count[letter - 'a']++;
		unsigned short temp = (cnt << 8) + letter;
		return temp;
	}

  int random(int min, int max);

  template<typename T>
  bool shuffle(T* array, int length);

	public:
	
	Boggle():board(NULL), length(0), width(0) {
		memset(count, 0, sizeof(count));
    srand(time(NULL));
	}

	~Boggle() {
		for(int i=0 ; i < length ; i++) {
			delete [] board[i];
		}
		delete [] board;
	}

  // board and graph api
  bool generateAndLoadBoard(char* board, int length, int width);
  bool generateBoard(char* board, int length, int width);
	bool loadBoard(char** board, int length, int width);
	void printGraph();
	void printBoard();
	void checkAnswers(std::string str[], int length, int* ans);

  // dictionary api
  bool addWordToDict(std::string& word);
  bool wordExistsInDict(std::string& word);
  unsigned int dictionary_size();

};

const char* Boggle::boggle_dices[MAX_DICES] = \
{
  "aaciot", //1
  "ahmors",
  "egkluy",
  "abilty",
  "acdemp", //5
  "egintv",
  "gilruw",
  "elpstu",
  "denosw",
  "acelrs", //10
  "abjmoq",
  "eefhiy",
  "ehinps",
  "dknoty",
  "adenvz", //15
  "biforx"
};

int Boggle::random(int MIN, int MAX) {
  double x = ((double)rand()/(RAND_MAX + 1));
  int mult = (MAX - MIN) + 1;
  int rnum = (x*mult); 
  if(rnum < 0) rnum = -rnum;
  if(rnum < MIN || rnum > MAX) {
    fprintf(stderr, "random number out of bounds\n");
    rnum = 0;
  }
  return rnum;
}

template<typename T>
bool Boggle::shuffle(T* array, int length)
{
  int swapx, swapy;
  for(int i = 0; i < length; i++ ) {
    swapx = random(0,length-1);
    swapy = random(0,length-1);
    T temp = array[swapx];
    array[swapx] = array[swapy];
    array[swapy] = temp;
  }
  return true;
}

unsigned int Boggle::dictionary_size() {
  return dict.total_size();
}

bool Boggle::wordExistsInDict(std::string& word) {
  return dict.exists(word.c_str(), word.length());
}

bool Boggle::addWordToDict(std::string& word) {
  return dict.add(word.c_str(), word.length());
}

bool Boggle::generateAndLoadBoard(char* board, int length, int width) {
  // call generateBoard and loadBoard
  bool result = true;
  result &= generateBoard(board, length, width);

  char** dptr_board = new char*[length];

  // convert char* to char**
  for(int i=0; i < length ; i++) {
    dptr_board[i] = &(board[i*width]);
  }
  
  result &= loadBoard(dptr_board, length, width);
  delete [] dptr_board;
  return result;
}

bool Boggle::generateBoard(char* board, int length, int width) {
  
  shuffle(boggle_dices, MAX_DICES);
  
  int total = length*width;
  while(total){
    int index = total-1;
    board[index] = (boggle_dices[index%16])[random(0,5)];
    total--;
  }
  return true;
}

void Boggle::checkAnswers(std::string str[], int length, int* ans) {
	for(int i = 0; i < length ; i++) {
		int len = str[i].length();
		short x[len];
		unsigned char tcnt[len];
		unsigned char temp[sizeof(count)];
		for(int k=0; k < (int)sizeof(count); k++) {
			if(count[k])
				temp[k] = count[k] -1;
			else
				temp[k] = count[k];
		}

		SPCounter<unsigned char> cnt(temp, sizeof(temp));
		memset(tcnt, 0, sizeof(tcnt));

		for(int k=0; k < len ; k++)
			tcnt[k] = str[i].at(k) - 'a';
			
		cnt.setIndexes(tcnt, sizeof(tcnt));
		// permute over all possibilities
		while(cnt.next(tcnt)) {
			for(int j = 0; j < len; j++) {
				x[j] = (tcnt[j] << 8) + str[i].at(j);
			}

			if(ans[i] = boggle_board.pathExists(x, len)){
				break;
			}
		}

    // check if dictionary has a word for it
    if(!wordExistsInDict(str[i])) {
      if(ans[i] == SUCCESS) 
        ans[i] = NO_SUCH_WORD;
      else 
        ans[i] = NO_PATH_NO_WORD;
    }
	}
}

void Boggle::printBoard() {
	std::string line(60,'-');
	std::cout << line << std::endl << std::endl;
	for(int i=0; i < length; i++) {
		for(int j=0 ; j < width; j++) {
			std::cout << board[i][j] << " ";
		}
		std::cout << std::endl;
	}
	std::cout << std::endl << line << std::endl;
}

namespace {
void printHelper(short& a, short& b) {
	std::cout << (char)(a&0xFF) << " - " << (char)(b&0xFF) << std::endl;
}
}
void Boggle::printGraph() {
	boggle_board.printAllConnections(printHelper);
}

bool Boggle::loadBoard(char** b, int l, int w) 
{
	short keys[l][w];

	if(l >= 10 || w >= 10) {
		fprintf(stderr, "Can not have more than 9x9 board\n");
		return false;
	}

  // if board is not NULL
  // delete the old one 
	board = new char*[l];
	for(int k=0;k < l;k++){
		board[k] = new char[w];
	}
	length = l;
	width = w;

	// added character on board to graph
	for(int i=0 ; i < l ; i++)
	{
		for(int j=0 ; j < w ; j++)
		{
			if(!isalpha(b[i][j])) {
				fprintf(stderr, "Unprintable Character\n");
				return false;
			}
			board[i][j] = b[i][j];
			keys[i][j] = returnKey(b[i][j], i, j);
			if(!boggle_board.addNode(keys[i][j])) {
				fprintf(stderr, "Cannot ever happen\n");
				fprintf(stderr, "Key: %d " \
					"Letter:%d " \
					"i:%d j:%d\n", keys[i][j], 
					b[i][j], i, j);
				return false;
			}
		}
	}

	// create connections
	for(int i=0 ; i < l ; i++)
	{
		for(int j=0 ; j < w ; j++)
		{
			short c = keys[i][j];
			
			if(i>0 && j>0) {
				short c1 = keys[i-1][j-1];
				boggle_board.createConnection(c,c1,Graph<short>::ONE_WAY);
			}
			if(i>0) {
				short c2 = keys[i-1][j];
				boggle_board.createConnection(c,c2,Graph<short>::ONE_WAY);
			}
			if(i>0 && j<(w-1)) {
				short c3 = keys[i-1][j+1];
				boggle_board.createConnection(c,c3,Graph<short>::ONE_WAY);
			}
			if(j>0){
				short c4 = keys[i][j-1];
				boggle_board.createConnection(c,c4,Graph<short>::ONE_WAY);
			}
			if(j<(w-1)) {
				short c5 = keys[i][j+1];
				boggle_board.createConnection(c,c5,Graph<short>::ONE_WAY);
			}
			if(i<(l-1) && j>0) {
				short c6 = keys[i+1][j-1];
				boggle_board.createConnection(c,c6,Graph<short>::ONE_WAY);
			}
			if(i<(l-1)){
				short c7 = keys[i+1][j];
				boggle_board.createConnection(c,c7,Graph<short>::ONE_WAY);
			}
			if(i<(l-1) && j<(w-1)) {
				short c8 = keys[i+1][j+1];
				boggle_board.createConnection(c,c8,Graph<short>::ONE_WAY);
			}
		}
	}
  return true;
}

#endif
